package com.learn.algorithm.recursive;

import java.util.HashSet;
import java.util.Set;

// https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
public class PrintAllSubString {

    public static void main(String[] args) {
        String[] result = generatePermutation2("ab");
        for (String s : result) {
            System.out.println(s);
        }
    }

    public static String[] generatePermutation(String str) {
        char[] s = str.toCharArray();
        StringBuilder builder = new StringBuilder();
        Set<String> set = new HashSet<>();
        collect(s, 0, builder, set);
        String[] ans = new String[set.size()];
        int i = 0;
        for (String cur : set) {
            ans[i++] = cur;
        }
        return ans;
    }

    public static void collect(char[] target, int i, StringBuilder path, Set<String> result) {
        if (i == target.length) {
            // 收集结果
            result.add(path.toString());
        } else {
            // 要i位置的字符
            path.append(target[i]);
            // 要i位置的字符继续递归
            collect(target, i + 1, path, result);

            // 不要要i位置的字符
            path.deleteCharAt(path.length() - 1);
            // 不要i位置的字符继续递归
            collect(target, i + 1, path, result);
        }
    }

    public static String[] generatePermutation2(String str) {
        char[] s = str.toCharArray();
        Set<String> set = new HashSet<>();
        char[] path = new char[str.length()];
        collect2(s, 0, path, 0, set);
        String[] ans = new String[set.size()];
        int i = 0;
        for (String cur : set) {
            ans[i++] = cur;
        }
        return ans;
    }

    public static void collect2(char[] target, int i, char[] path, int size, Set<String> result) {
        if (i == target.length) {
            // 收集结果
            result.add(String.valueOf(path, 0, size));
        } else {
            path[size] = target[i];
            collect2(target, i + 1, path, size + 1, result);
            collect2(target, i + 1, path, size, result);
        }
    }

}
